package baseclass.j_dp.dp.oneZeroBag;

import java.util.Arrays;

/**
 * 给一个非负数数组和目标和sum，求该数组能组成sum的种数。
 * 同一个位置元素不可重复利用。
 *
 * @date 2020/3/2 18:16
 */
public class Code04_SumTargetCountInArr {
    public static int m1(int[] arr, int sum, int aim, int i) {
        if(arr == null || arr.length == 0) return 0;
        if (aim == sum) {
            return 1;
        }
        if (i >= arr.length || sum > aim){
            return 0;
        }
        return m1(arr, sum, aim, i + 1) +
                m1(arr, sum + arr[i], aim, i + 1);
    }

    /**
     * memo[i][j]表示 决策完第i号元素，和为j的次数
     */
    public static int m2(int[]arr,int aim){
        if(arr == null || arr.length == 0) return 0;
        int sum = 0;
        for(int e : arr) sum += e;
        if(sum < aim) return 0;
        int[][] memo = new int[arr.length][sum+1];
        for (int i = 0; i < memo.length; i++) {
            Arrays.fill(memo[i],-1);
        }
        return doM2(arr,0,aim,0,memo);
    }
    private static int doM2(int[] arr, int sum, int aim, int i, int[][] memo) {
        if (aim == sum) {
            return 1;
        }
        if (i >= arr.length || sum > aim){
            return 0;
        }
        if(memo[i][sum] != -1)return memo[i][sum];

        return memo[i][sum] = doM2(arr, sum, aim, i + 1, memo) +
                doM2(arr, sum + arr[i], aim, i + 1, memo);
    }

    /**
     * 动态规划 dp[i][j]表示 决策完第i号元素，和为j的次数
     */
    public static int m3(int[]arr,int aim){
        if(arr == null || arr.length == 0) return 0;
        int sum = 0;
        for(int e : arr) sum += e;
        if(sum < aim) return 0;
        //并不关心大于aim的
        int[][]dp = new int[arr.length][aim+1];
        //第0位置可以组成 0或nums[0]
        dp[0][0] = 1;
        //注意要考虑nums[0]= 0，那么要0和都不要0都是0，但是是两种选择所以这里是 +=
        if (arr[0] <= aim)
            dp[0][arr[0]] += 1;

        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j <= aim ; j++) {
                dp[i][j] = dp[i-1][j];
                if(j - arr[i] >= 0)
                    dp[i][j] = dp[i][j] + dp[i-1][j-arr[i]];
            }

        }
        return dp[arr.length-1][aim];
    }

    /**
     * 空间优化
     */
    public static int m4(int[]arr,int aim){
        if(arr == null || arr.length == 0) return 0;
        int sum = 0;
        for(int e : arr) sum += e;
        if(sum < aim) return 0;
        int[]dp = new int[aim+1];
        //第0位置可以组成 0或nums[0]
        dp[0] = 1;
        //注意要考虑nums[0]= 0，那么要0和都不要0都是0，但是是两种选择所以这里是 +=
        if (arr[0] <= aim)
            dp[arr[0]] += 1;

        for (int i = 1; i < arr.length; i++) {
           /* for (int j = aim; j >= 0 ; j--) {
                if(j - arr[i] >= 0)
                    dp[j] = dp[j] + dp[j-arr[i]];
            }*/
            //上面代码等价于
            for (int j = aim; j >= arr[i] ; j--) {
                dp[j] = dp[j] + dp[j-arr[i]];
            }
        }
        return dp[aim];
    }

    public static void main(String[] args) {
        int[] arr = {1, 1 ,1, 1,1};
        System.out.println(m1(arr, 0, 3, 0));
        System.out.println(m2(arr, 3));
        System.out.println(m3(arr, 3));
        System.out.println(m4(arr, 3));

        /*for (int i = 0; i < 10000; i++) {
            arr = generateRandomArray(10, 20);
            int aim = (int) (Math.random() * 21);
            try {
                if (m3(arr, aim) != m4(arr, aim)) {
                    System.out.println("出错的数组:" + Arrays.toString(arr));
                    break;
                }
            } catch (Exception e) {
                System.out.println(Arrays.toString(arr));
                break;
            }

        }*/

    }

    // for test
    private static int[] generateRandomArray(int maxSize, int maxValue) {
        //产生 [0-maxsize]随机长度的数组
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            //随机产生数据
            arr[i] = (int) ((maxValue + 1) * Math.random());
        }
        return arr;
    }
}
